package com.sheng.leetcode.year2022.month07.day10;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/07/12
 *
 * 741. 摘樱桃
 *
 * 一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：
 * 0 表示这个格子是空的，所以你可以穿过它。
 * 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
 * -1 表示这个格子里有荆棘，挡着你的路。
 * 你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：
 * 从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）；
 * 当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
 * 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）；
 * 如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。
 *
 * 示例 1:
 * 输入: grid =
 * [[0, 1, -1],
 *  [1, 0, -1],
 *  [1, 1,  1]]
 * 输出: 5
 * 解释：
 * 玩家从（0,0）点出发，经过了向下走，向下走，向右走，向右走，到达了点(2, 2)。
 * 在这趟单程中，总共摘到了4颗樱桃，矩阵变成了[[0,1,-1],[0,0,-1],[0,0,0]]。
 * 接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了1颗樱桃。
 * 在旅程中，总共摘到了5颗樱桃，这是可以摘到的最大值了。
 * 说明:
 *
 * grid 是一个 N * N 的二维数组，N的取值范围是1 <= N <= 50。
 * 每一个 grid[i][j] 都是集合 {-1, 0, 1}其中的一个数。
 * 可以保证起点 grid[0][0] 和终点 grid[N-1][N-1] 的值都不会是 -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/cherry-pickup
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0741 {

    @Test
    public void test01() {
        int[][] grid = {{0, 1, -1},{1, 0, -1},{1, 1, 1}};
        System.out.println(new Solution().cherryPickup(grid));
    }

}
//class Solution {
//    public int cherryPickup(int[][] grid) {
//        return 0;
//    }
//}

//为了方便，我们令 grid 为 g，同时调整矩阵横纵坐标从 1 开始。
//原问题为先从左上角按照「只能往下 + 只能往右」的规则走到右下角，
//然后再按照「只能往上 + 只能往左」的规则走回左上角，途径的值为 1 的格子得一分（只能得分一次，得分后置零），
//同时不能经过值为 -1 的格子。
//其中第二趟的规则等价于按照第一趟的规则从左上角到右下角再走一遍，再结合每个位置的只能得分一次，
//可以将原问题等价于：两个点从左上角开始同时走，最终都走到右下角的最大得分。
//定义 f[k][i1][i2] 为当前走了 k 步（横纵坐标之和），且第一个点当前在第 i1 行，第二点在第 i2 行时的最大得分，
//最终答案为 f[2n][n][n]，同时有 f[2][1][1] = g[0][0] 的起始状态。
//由于两个点是同时走（都走了 k 步），结合「只能往下 + 只能往右」的规则，
//可直接算得第一个点所在的列为 j1 = k - i1，第二点所在的列为 j2 = k - i2。
//不失一般性考虑 f[k][i1][i2] 该如何转移，两个点均有可能走行或走列，
//即有 4 种前驱状态：f[k - 1][i1 - 1][i2]、f[k - 1][i1 - 1][i2 - 1]、f[k - 1][i1][i2 - 1] 和 f[k - 1][i1][i2]，
//在四者中取最大值，同时当前位置 (i1, j1) 和 (i2, j2) 的得分需要被累加，
//假设两者得分别为 A 和 B，若两个位置不重叠的话，可以同时累加，否则只能累加一次。
//
//一些细节：为了防止从值为 -1 的格子进行转移影响正确性，我们需要先将所有 f[k][i1][i2] 初始化为负无穷。
//
class Solution {
    static int N = 55, INF = Integer.MIN_VALUE;
    static int[][][] f = new int[2 * N][N][N];
    public int cherryPickup(int[][] g) {
        int n = g.length;
        for (int k = 0; k <= 2 * n; k++) {
            for (int i1 = 0; i1 <= n; i1++) {
                for (int i2 = 0; i2 <= n; i2++) {
                    f[k][i1][i2] = INF;
                }
            }
        }
        f[2][1][1] = g[0][0];
        for (int k = 3; k <= 2 * n; k++) {
            for (int i1 = 1; i1 <= n; i1++) {
                for (int i2 = 1; i2 <= n; i2++) {
                    int j1 = k - i1, j2 = k - i2;
                    if (j1 <= 0 || j1 > n || j2 <= 0 || j2 > n) {
                        continue;
                    }
                    int A = g[i1 - 1][j1 - 1], B = g[i2 - 1][j2 - 1];
                    if (A == -1 || B == -1) {
                        continue;
                    }
                    int a = f[k - 1][i1 - 1][i2], b = f[k - 1][i1 - 1][i2 - 1], c = f[k - 1][i1][i2 - 1], d = f[k - 1][i1][i2];
                    int t = Math.max(Math.max(a, b), Math.max(c, d)) + A;
                    if (i1 != i2) {
                        t += B;
                    }
                    f[k][i1][i2] = t;
                }
            }
        }
        return f[2 * n][n][n] <= 0 ? 0 : f[2 * n][n][n];
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/cherry-pickup/solution/by-ac_oier-pz7i/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
